{
 "cells": [
  {
   "cell_type": "markdown",
   "id": "f845db1e",
   "metadata": {},
   "source": [
    "## 美团第一次机试\n",
    "- 一共四道编程题， 四道选择题\n",
    "- 考试时长2h"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "2f247392",
   "metadata": {},
   "source": [
    "### 第一题 字母串匹配问题\n",
    "> 问题描述： 字符串S只包含小写字母，长度为n； 字符串s包含\"\\*\"和小写字母，长度为m；字符\"\\*\" 可以匹配任意字符，问S中有多少个子段可以被s匹配\n",
    "\n",
    "> 输入描述： 第一行 输入“n m”； 第二行输入长度为n的字符串 S；第三行输入长度为m的字符串 s  \n",
    "     \n",
    "\n",
    "> 对于所有输入： $1 \\le m \\le n \\le 2000 $\n",
    "\n",
    "\n",
    "**样例输入**\n",
    "```\n",
    "7 3\n",
    "abcaacc\n",
    "a*c\n",
    "```\n",
    "\n",
    "**样例输入**\n",
    "```\n",
    "3\n",
    "```\n",
    "**提示**\n",
    "```\n",
    "可以对abc，aac，acc匹配a*c\n",
    "```"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "id": "cd31a75e",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "7 3\n",
      "abcaacc\n",
      "a*c\n",
      "3\n"
     ]
    }
   ],
   "source": [
    "# coding = utf-8\n",
    "[n,m] = list(map(int, input().split()))\n",
    "S = input()\n",
    "s = input()\n",
    "\n",
    "res = 0\n",
    "for i in range(n-m+1):\n",
    "    flag = True\n",
    "    for j in range(m):\n",
    "        if s[j]=='*':\n",
    "            continue\n",
    "        elif S[i+j]!=s[j]:\n",
    "            flag = False\n",
    "            break\n",
    "    if flag: res += 1\n",
    "print(res)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "a923c3ec",
   "metadata": {},
   "source": [
    "## 第二题  珠宝序列问题\n",
    "\n",
    "> 问题描述: n个宝石,编号为1~n,编号不会随着宝石位置变化而改变, 小美对宝石顺序进行微调,每次选择一个编号x,将其放在宝石的最左侧,不改变其他宝石的相对位置, 一共进行了m次, 问最终宝石的顺序是什么\n",
    "\n",
    "> 输入描述: 第一行两个正整数: n m;    第二行m个数: x1, x2, ..., xm;  $1 \\le m,n \\le 50000 $, $1 \\le x_i \\le n$\n",
    "\n",
    "> 输出描述: 输出一行整数, 表示答案,\n",
    "\n",
    "**样例输入**\n",
    "```\n",
    "5 3\n",
    "2 3 4\n",
    "```\n",
    "\n",
    "**样例输出**\n",
    "```\n",
    "4 3 2 1 5\n",
    "```\n",
    "\n",
    "**提示**\n",
    "```\n",
    "第一次微调后: 2 1 3 4 5\n",
    "第二次微调后: 3 2 1 4 5\n",
    "第三次微调后: 4 3 2 1 5\n",
    "```"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "id": "169b32dd",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "5 3\n",
      "4 3 1\n",
      "1 3 4 2 5 "
     ]
    }
   ],
   "source": [
    "# 感觉这个方法没错,但是实际测试的时候只通过 82%\n",
    "# coding=uft-8\n",
    "\n",
    "[n,m] = list(map(int,input().split()))\n",
    "xs = list(map(int, input().split()))\n",
    "X = list(range(1,n+1))\n",
    "\n",
    "def fun(n,m,xs,X):\n",
    "    for x in xs:\n",
    "        X.pop(X.index(x))\n",
    "        X.insert(0,x)\n",
    "    return X\n",
    "X = fun(n,m,xs,X)\n",
    "for item in X:\n",
    "    print(item,end=' ')\n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "id": "e3638e82",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "5 3\n",
      "5 4 1\n",
      "1 4 5 2 3 "
     ]
    }
   ],
   "source": [
    "# coding=utf-8\n",
    "# 使用链表的方法\n",
    "\n",
    "[n,m] = list(map(int,input().split()))\n",
    "xs = list(map(int, input().split()))\n",
    "X = list(range(1,n+1))\n",
    "\n",
    "class Node():\n",
    "    def __init__(self, value=None, next=None):\n",
    "        self.value = value\n",
    "        self.next = next\n",
    "\n",
    "def fun(n,m,xs,X):\n",
    "    head = Node(value=None)\n",
    "    pos = head\n",
    "    for i in range(1,n+1):\n",
    "        node = Node(value=i)\n",
    "        pos.next = node\n",
    "        pos = pos.next\n",
    "\n",
    "    \n",
    "    def change(head,val):\n",
    "        # find val\n",
    "        pos = head\n",
    "        while (pos.next):\n",
    "            if pos.next.value==val:\n",
    "                pos.next = pos.next.next  # remove pos.next\n",
    "                break\n",
    "            pos = pos.next\n",
    "        node = Node(value=val)  # 添加新节点到最左侧\n",
    "        node.next = head.next\n",
    "        head.next = node\n",
    "    \n",
    "    for x in xs:\n",
    "        change(head, x)\n",
    "        \n",
    "    return head\n",
    "\n",
    "head = fun(n,m,xs,X)\n",
    "pos = head\n",
    "while(pos.next):\n",
    "    print(pos.next.value,end=' ')\n",
    "    pos = pos.next\n",
    "    \n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "id": "84ceac4b",
   "metadata": {
    "scrolled": true
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "5 3\n",
      "4 3 1\n",
      "1 3 4 2 5 "
     ]
    }
   ],
   "source": [
    "# test\n",
    "[n,m] = list(map(int, input().split()))\n",
    "xs = list(map(int,input().split()))\n",
    "\n",
    "class Note:\n",
    "    def __init__(self, val=None, next=None):\n",
    "        self.val = val\n",
    "        self.next = next\n",
    "\n",
    "\n",
    "def fun(n,m,xs):\n",
    "    head = Note(val=None)\n",
    "    pos = head\n",
    "    for i in range(1,n+1):\n",
    "        noteTmp = Note(val=i)\n",
    "        pos.next = noteTmp\n",
    "        pos = pos.next\n",
    "    \n",
    "    def change(head,x):\n",
    "        pos = head\n",
    "        while(pos.next):\n",
    "            if pos.next.val == x:\n",
    "                pos.next = pos.next.next\n",
    "                break\n",
    "            pos = pos.next\n",
    "        note = Note(val=x)\n",
    "        note.next = head.next\n",
    "        head.next = note\n",
    "    \n",
    "    for x in xs:\n",
    "        change(head,x)\n",
    "        \n",
    "    return head\n",
    "\n",
    "head = fun(n,m,xs)\n",
    "pos = head\n",
    "while(pos.next):\n",
    "    print(pos.next.val, end=' ')\n",
    "    pos = pos.next"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "84ed78a7",
   "metadata": {},
   "source": [
    "## 第三题   字符串裁剪问题\n",
    "> 问题描述：一个只含有小写英文字母的字符串S，其长度为n，可以在S的任意位置裁剪，给定m个字串，问存在多少种裁剪方式，使得S可以被裁剪出m个不相交的字串，与给定的字串一一对应（一一对应值，字符串的顺序也一样）\n",
    "\n",
    "> 输入描述： 第一行两个正整数：n m；    第二行长度为n的字符串 S；   第三行m个空格隔开的正整数，x1 x2 ... xm;   接下来m行，每一行都是一个字符串，字符串的长度分别为 x1 x2 ... xm；   $ 1\\le m \\le 9 $  $1 \\le n \\le 20$, $ 1 \\le x_i \\le n $; $\\sum\\nolimits_{i = 1}^m {{x_i} = n} $\n",
    "\n",
    "> 输出描述： 如果存在这样的方案， 输出方案总数， 如果不存在输出0；两种方案 A， B 不同，当且仅当A存在一个裁剪位置 i， 而B未在i处裁剪；  例如 aaa|aaa  和 aaa|aaa 是同一个方案， 而 aa|aaaa 和 aaaa|aa 是不同方案\n",
    "\n",
    "**样例输入**\n",
    "```\n",
    "6 2\n",
    "aaaaaa\n",
    "4 2\n",
    "aaaa\n",
    "aa\n",
    "```\n",
    "\n",
    "**样例输出**\n",
    "```\n",
    "2\n",
    "```\n",
    "\n",
    "**提示**\n",
    "```\n",
    "两种方案 （aa|aaaa）,(aaaa|aa)\n",
    "```"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "id": "f43ae21e",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "6 2\n",
      "aaaaaa\n",
      "3 3\n",
      "aaa\n",
      "aaa\n",
      "1\n"
     ]
    }
   ],
   "source": [
    "## 把S分割问题转化为多个X字符串组合问题，然后去重\n",
    "# 深度优先遍历出 所有组合方式，\n",
    "# 计算组合对应的切割位点，这一步是为了去重\n",
    "# 比较组合和S是否一致，如果一致，记录该组合对应的切割位点\n",
    "# 遍历比较完毕，统计非重复切割位点的数目，返回\n",
    "# 记得如果没有任何匹配，返回-1\n",
    "\n",
    "# coding=utf-8\n",
    "[n,m]=list(map(int,input().split()))\n",
    "S = list(input())\n",
    "xs = list(map(int,input().split()))\n",
    "X = []\n",
    "for i in range(m):\n",
    "    X.append(list(input()))\n",
    "\n",
    "def findAllcomb(m):\n",
    "    curLst = []\n",
    "    resLst = list(range(m))\n",
    "    res = []\n",
    "    \n",
    "    def rfun(curLst,resLst):\n",
    "        if len(resLst)==0:\n",
    "            nonlocal res\n",
    "            res.append(curLst[::])\n",
    "            return\n",
    "        for i in range(len(resLst)-1,-1,-1):\n",
    "            item = resLst.pop(i)\n",
    "            curLst.append(item)\n",
    "            rfun(curLst,resLst)\n",
    "            curLst.pop(-1)\n",
    "            resLst.append(item)\n",
    "    \n",
    "    rfun(curLst, resLst)\n",
    "    \n",
    "    def compareStr(S,re,X,xs):\n",
    "        comX = []\n",
    "        cutPos = []\n",
    "        pos = -1\n",
    "        for r in re:\n",
    "            comX = comX+X[r]\n",
    "            pos = pos + xs[r]\n",
    "            cutPos.append(pos)\n",
    "        if comX == S:\n",
    "            return [True, cutPos]\n",
    "        else:\n",
    "            return [False, cutPos]\n",
    "        \n",
    "    count = 0\n",
    "    countCutPos = []\n",
    "    for re in res:\n",
    "        [flag, cutPos] = compareStr(S,re,X,xs)\n",
    "        if flag and cutPos not in countCutPos:\n",
    "            countCutPos.append(cutPos)\n",
    "            \n",
    "    count = len(countCutPos)\n",
    "    return count\n",
    "\n",
    "count = findAllcomb(m)\n",
    "if count==0:\n",
    "    count = -1\n",
    "print(count)                     "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 25,
   "id": "9c829fed",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "6 2\n",
      "aaaaaa\n",
      "3 3\n",
      "aaa\n",
      "aaa\n",
      "[['aaa', 'aaa'], ['aaa', 'aaa']]\n",
      "{('aaa', 'aaa')}\n"
     ]
    }
   ],
   "source": [
    "## BFS\n",
    "# 没有考虑重复的情况，e.g.: aaa|aaa, aa\\aa\\aa\n",
    "# coding=utf-8\n",
    "_author_= \"kongweiren\"\n",
    "from copy import copy\n",
    "\n",
    "[n,m]=list(map(int,input().split()))\n",
    "S = input()\n",
    "xs = list(map(int,input().split()))\n",
    "ss = []\n",
    "for i in range(m):\n",
    "    ss.append(input())\n",
    "\n",
    "def tailor(n,m,S,xs,ss):\n",
    "    res = []\n",
    "    xss = list(zip(xs,ss))\n",
    "    stacks = [(S,xss,[])]\n",
    "    \n",
    "    while stacks:\n",
    "        rem_S, rem_xss, path = stacks.pop()\n",
    "        if len(path) == m:\n",
    "            res.append(path)\n",
    "        else:\n",
    "            for x,s in rem_xss:\n",
    "                if rem_S[:x] == s:\n",
    "                    tmp_rem_xss = copy(rem_xss)\n",
    "                    tmp_path = copy(path)\n",
    "                    tmp_rem_xss.remove((x,s))\n",
    "                    tmp_path.append(s)\n",
    "                    stacks.append((rem_S[x:], tmp_rem_xss, tmp_path))\n",
    "    print(res)\n",
    "    res = set(list(map(tuple, res)))\n",
    "    return res\n",
    "            \n",
    "\n",
    "res = tailor(n,m,S,xs,ss)\n",
    "print(res)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "9a2c958d",
   "metadata": {},
   "source": [
    "## 第四题  机器人收衣服问题\n",
    "> 问题描述： n件衣服从左到右排列，编号分别为1~n， 每件衣服旁边有一台机器人，第i个位置的机器人收衣服需要消耗电量pi，用时ti， 位置i的机器人收完自己位置的衣服，如果右侧还有衣服，他会继续耗时ti，收这件衣服，直到右侧的衣服已经被其他机器人收取了或者已经没有衣服了，现在小明共有电量b，他准备在0时刻启动想要启动的所有机器人，之后不再启动新的机器人，启动机器人所需的总电量不能超过b，问最快多久能收完衣服，如果无论如何都收不完衣服输出-1\n",
    "\n",
    "> 输入描述： 第一行两个正整数：n b；    第二行包含n个数：p1 p2 p3 ...pn;  第三行包含n个数 t1 t2 t3 ... tn;  $1 \\le n \\le 1000$;  $1 \\le pi \\le 100$;   $b \\le 10^5$\n",
    "\n",
    "> 输出描述： 输出最短时间\n",
    "\n",
    "**样例输入**\n",
    "```\n",
    "3 5\n",
    "1 2 3\n",
    "7 5 3\n",
    "```\n",
    "**样例输入**\n",
    "```\n",
    "10\n",
    "```\n",
    "\n",
    "**提示**\n",
    "```\n",
    "方案1：同时启动第一个机器人和第二个机器人，耗电量： 1+2=3； 花费时间：max(7,5*2)=10\n",
    "方案2：同时启动第一个机器人和第三个机器人，耗电量： 1+3=4； 花费时间：max(7*2,3)=14\n",
    "\n",
    "```"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 27,
   "id": "6c262a26",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "3 5\n",
      "1 2 3\n",
      "7 5 3\n",
      "10\n"
     ]
    }
   ],
   "source": [
    "# 参考升级的背包问题的解法\n",
    "# 构建一个二维数组，b+1行，2列， 第一列当前状态最小时间，第二列存储一个列表，放置与最小时间对应的所有启动机器人的序号\n",
    "# stacks=[timec,[]]\n",
    "# 遍历每一个样本， 更新上面的二维状态数组\n",
    "from copy import copy\n",
    "[n,b] = list(map(int,input().split()))\n",
    "P = list(map(int,input().split()))\n",
    "T = list(map(int,input().split()))\n",
    "\n",
    "def robot(n,b,P,T):\n",
    "    stacks = []\n",
    "    for i in range(b+1):\n",
    "        stacks.append([-1,[]])\n",
    "    \n",
    "\n",
    "    if P[0] <= b:  # 第一个机器人必须启动\n",
    "        stacks[P[0]][0] = T[0]*n\n",
    "        stacks[P[0]][1].append(0)\n",
    "    else:  # 第一个不启动，无法收完衣服\n",
    "        return -1\n",
    "    \n",
    "    count = P[0]\n",
    "    for i in range(1,n):\n",
    "        p = P[i]\n",
    "        \n",
    "        if p>b-P[0]:\n",
    "            continue\n",
    "        for j in range(P[0],min(count+1,b-p+1)): # 只遍历到当前最高点，已遍历机器的电量和\n",
    "            if stacks[j][0]!= -1:\n",
    "                path = copy(stacks[j][1])\n",
    "                path.append(i)\n",
    "                timeC = (path[1]-path[0])*T[path[0]]\n",
    "                if len(path)==2:\n",
    "                    timeC = max(timeC,T[path[1]]*(n-path[1]))\n",
    "                else:\n",
    "                    for ii in range(1,len(path)-1):\n",
    "                        timeC = max(timeC,(path[ii+1]-path[ii])*T[path[ii]])\n",
    "                    timeC = max(timeC, (n-path[-1])*T[path[-1]])\n",
    "                if stacks[p+j][0]>timeC or stacks[p+j][0]==-1: # 方案时间更短才更新状态列表\n",
    "                    stacks[p+j][0] = timeC\n",
    "                    stacks[p+j][1] = path\n",
    "        count += p\n",
    "    minTime = float('inf')\n",
    "    for stack in stacks:\n",
    "        if stack[0]!=-1:\n",
    "            minTime = min(minTime,stack[0])\n",
    "    return minTime\n",
    "\n",
    "print(robot(n,b,P,T))\n",
    "                \n",
    "                \n",
    "                \n",
    "                \n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "67f5d342",
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3 (ipykernel)",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.9.12"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}
